//https://leetcode.cn/problems/find-if-path-exists-in-graph/submissions/581227357/

class UnionFind{
public:
    UnionFind(int n){
        parent = vector<int>(n);//每个节点的父节点
        rank = vector<int>(n);//每个节点的秩（树的高度），用于优化合并操作
        for(int i = 0;i< n;++i){
            parent[i] = i;//对于每个节点 i，设置其父节点为自身
        }
    }

    void uni(int x,int y){//合并节点 x 和节点 y 所在的集合
        int rootx = find(x);
        int rooty = find(y);//找到节点 x 和 y 的根节点 rootx 和 rooty
        if(rootx != rooty){
            if(rank[rootx] > rank[rooty]){
                parent[rooty] = rootx;
            }else if(rank[rootx] < rank[rooty]){
                parent[rootx] = rooty;
            }else{
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }
    int find(int x){//递归寻找节点 x 的根节点（祖先）
        if(parent[x] != x){
            parent[x] = find(parent[x]);//在递归返回时，将节点 x 直接连接到其根节点上，优化后续查找效率
        }
        return parent[x];
    }
    bool connect(int x,int y){//检查节点 x 和节点 y 是否连通
        return find(x)==find(y);//连通的判断依据是两节点是否有相同的根节点
    }
private:
    vector<int> parent;
    vector<int> rank;
};

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if(source == destination){return true;}
        UnionFind uf(n);//初始化并查集
        for(auto edge : edges){
            uf.uni(edge[0],edge[1]);//遍历所有的边 edges，对于每一条边 [u, v]，将节点 u 和 v 合并
        }
        return uf.connect(source,destination);//判断 source 和 destination 是否连通
    }
};